c23b0b4ca1b662493b1646cfe95451df9c485e3c,src/it/unimi/dsi/sux4j/mph/HypergraphSolver.java,HypergraphSolver,directHyperedges,#number[][]#number[]#number[]#number[]#number[]#number[]#number#,507

Before Change


					update( queue, posInQueue, priority, v0, update );
				}
				if ( ! isHinge[ v1 ] ) {
					update( queue, posInQueue, priority, v1, update );
				}
				if ( ! isHinge[ v2 ] ) {
					update( queue, posInQueue, priority, v2, update );
				}
			}

			final int v0 = vertex0[ edge ];
			final int v1 = vertex1[ edge ];
			final int v2 = vertex2[ edge ];

			assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;

			d[ v0 ]--;
			if ( ! isHinge[ v0 ] ) {
				update2( d, weight, queue, posInQueue, priority, edge, v0 );
			}

			d[ v1 ]--;
			if ( ! isHinge[ v1 ] ) {
				update2( d, weight, queue, posInQueue, priority, edge, v1 );
			}

			d[ v2 ]--;

After Change


	 */
	public static boolean directHyperedges( int[][] edges , int[] d , int[] vertex0 , int[] vertex1 , int[] vertex2 , int[] hinges  ) {
		final int numVertices = d.length;
		final int numEdges = vertex0.length;
		final int[] weight = new int[ numEdges ];
		final boolean[] isHinge = new boolean[ numVertices ];
		final boolean[] isDone = new boolean[ numEdges ];
		Arrays.fill( weight, 3 );

		if ( ASSERTS ) {
			final int[] testd = new int[ d.length ];
			for ( int i = 0; i < numEdges; i++ ) {
				testd[ vertex0[ i ] ]++;
				testd[ vertex1[ i ] ]++;
				testd[ vertex2[ i ] ]++;
			}
			if ( ! Arrays.equals( testd, d ) ) throw new AssertionError( "Degree array not valid: " + Arrays.toString( testd ) + " != " + Arrays.toString( d ) );
		}
		
		/* - queues of index 0,1,..,6 contains vertices with that priority.
		 * - the queue of index 7 contains all vertices with priority > 6. */
		final IntArrayList[] queue = new IntArrayList[ 8 ];
		for( int i = queue.length; i-- != 0; ) queue[ i ] = new IntArrayList();
		// For each vertex, its position in the queue it lives in.
		final int[] posInQueue = new int[ numVertices ];
				
		// Priorities, multiplied by 6 (so they are all integers)
		final int[] priority = new int[ numVertices ];
		for ( int i = 0; i < numVertices; i++ ) priority[ i ] += 2 * d[ i ];
		
		for ( int i = 0; i < d.length; i++ ) if ( d[ i ] > 0 ) {
			final IntArrayList q = queue[ Math.min( 7, priority[ i ] ) ];
			posInQueue[ i ] = q.size();
			q.add( i );
		}

		for ( int t = 0; t < numEdges; t++ ) {		
			// Find hinge by looking at the node with minimum priority
			int minPriority = 0;
			while( minPriority < 8 && queue[ minPriority ].isEmpty() ) minPriority++;
			if ( minPriority == 8 ) return false;
			final int hinge = queue[ minPriority ].popInt();
			int edge = -1;
			int minWeight = Integer.MAX_VALUE;
			for( int i = edges[ hinge ].length; i-- != 0; ) {
				final int e = edges[ hinge ][ i ];
				if ( ! isDone[ e ] && weight[ e ] < minWeight ) {
					edge = e;
					minWeight = weight[ e ];
				}
			}
			
			assert edge != -1;

			if ( ASSERTS ) {
				int minEdgeWeight = Integer.MAX_VALUE;
				int minEdge = -1;
				for( int i = 0; i < numEdges; i++ ) if ( ! isDone[ i ] ) {
					if ( vertex0[ i ] == hinge || vertex1[ i ] == hinge || vertex2[ i ] == hinge ) {
						if ( weight[ i ] < minEdgeWeight ) {
							minEdgeWeight = weight[ i ];
							minEdge = i;
						}
					}
					
				}
				if ( weight[ edge ] != weight[ minEdge ] ) throw new AssertionError( "Min edge " + t + ": " + minEdge + " != " + edge );
			}
			
			
			//System.err.println( "Round " + ( t - offset ) + ": found hinge " + hinge + " for edge " + edge + " (" + vertex0[ edge ] + ", " + vertex1[ edge ] + ", " + vertex2[ edge ] + ")" );
			if ( priority[ hinge ] > 6 ) {
				//System.err.println( "Hinge " + hinge + " priority: " + priority[ hinge ] );
				return false;
			}
			hinges[ edge ] = hinge;
			isHinge[ hinge ] = true;
			isDone[ edge ] = true;
			
			for( int i = edges[ hinge ].length; i-- != 0; ) {
				final int e = edges[ hinge ][ i ];
				if ( isDone[ e ] ) continue;
				final int v0 = vertex0[ e ];
				final int v1 = vertex1[ e ];
				final int v2 = vertex2[ e ];
				assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;

				final int update = -6 / weight[ e ] + 6 / --weight[ e ];
				
				if ( ! isHinge[ v0 ] ) increase( queue, posInQueue, priority, v0, update );
				if ( ! isHinge[ v1 ] ) increase( queue, posInQueue, priority, v1, update );
				if ( ! isHinge[ v2 ] ) increase( queue, posInQueue, priority, v2, update );
			}

			final int v0 = vertex0[ edge ];
			final int v1 = vertex1[ edge ];
			final int v2 = vertex2[ edge ];

			assert hinge == v0 || hinge == v1 || hinge == v2 : hinge + " != " + v0 + ", " + v1 + ", " + v2;

			d[ v0 ]--;
			if ( ! isHinge[ v0 ] ) decrease( queue, posInQueue, priority, d, v0, weight[ edge ] );

			d[ v1 ]--;
			if ( ! isHinge[ v1 ] ) decrease( queue, posInQueue, priority, d, v1, weight[ edge ] );